package com.lw.leetcode.back.b;

/**
 * Created with IntelliJ IDEA.
 * 1905. 统计子岛屿
 *
 * @author liw
 * @version 1.0
 * @date 2021/11/16 13:40
 */
public class CountSubIslands {

    public static void main(String[] args) {
        CountSubIslands test = new CountSubIslands();

        // 3
//        int[][] grid1 = {{1,1,1,0,0},{0,1,1,1,1},{0,0,0,0,0},{1,0,0,0,0},{1,1,0,1,1}};
//        int[][] grid2 = {{1,1,1,0,0},{0,0,1,1,1},{0,1,0,0,0},{1,0,1,1,0},{0,1,0,1,0}};

        // 3
        int[][] grid1 = {{1,0,1,0,1},{1,1,1,1,1},{0,0,0,0,0},{1,1,1,1,1},{1,0,1,0,1}};
        int[][] grid2 = {{0,0,0,0,0},{1,1,1,1,1},{0,1,0,1,0},{0,1,0,1,0},{1,0,0,0,1}};

        int i = test.countSubIslands(grid1, grid2);
        System.out.println(i);
    }

    private int[][] grid1;
    private int[][] grid2;
    private int a;
    private int b;

    public int countSubIslands(int[][] grid1, int[][] grid2) {
        this.grid1 = grid1;
        this.grid2 = grid2;
        this.a = grid1.length;
        this.b = grid1[0].length;
        int sum = 0;
        for (int i = 0; i < a; i++) {
            for (int j = 0; j < b; j++) {
                if (grid2[i][j] == 0) {
                    continue;
                }
                if (find(i, j)) {
                    sum++;
                }
            }
        }
        return sum;
    }


    private boolean find(int x, int y) {
        if (x < 0 || x == a || y < 0 || y == b) {
            return true;
        }
        int v = grid2[x][y];
        if (v == 0) {
            return true;
        }
        if (grid1[x][y] == 1) {
            grid2[x][y] = 0;
            boolean flag = find(x - 1, y);
            if (flag) {
                flag = find(x + 1, y);
            }
            if (flag) {
                flag = find(x, y - 1);
            }
            if (flag) {
                return find(x, y + 1);
            }
            grid2[x][y] = 1;
            find2(x, y);
            return false;
        } else {
            find2(x, y);
            return false;
        }
    }

    private void find2(int x, int y) {
        if (x < 0 || x == a || y < 0 || y == b) {
            return;
        }
        if (grid2[x][y] == 0) {
            return;
        }
        grid2[x][y] = 0;
        find2(x - 1, y);
        find2(x + 1, y);
        find2(x, y - 1);
        find2(x, y + 1);
    }

}
